package top.minuy.structure.tree.unifind;

import java.util.Random;

/**
 * @author Minuy
 * @time 17:18
 * @date 2021/10/31
 */
public class Test {
    /**
     * 测试并查集
     * @param uf 并查集
     * @param opTime 操作次数
     * @return 所需时间 单位：s
     */
    static double testUF(UF uf, int opTime) {
        Random r = new Random();
        int size = uf.getSize();
        long startTime = System.nanoTime();
        {
            int p, q;
            for (int i = 0; i < opTime; i++) {
                p = r.nextInt(size);
                q = r.nextInt(size);
                uf.unionElements(p, q);
            }
            for (int i = 0; i < opTime; i++) {
                p = r.nextInt(size);
                q = r.nextInt(size);
                uf.isConnected(p, q);
            }
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {
        int n = 10000000,op = 100000;
        System.out.println(String.format("size = %d, op = %d",n,op));

        UnionFindV1 u1 = new UnionFindV1(n);
        System.out.println("U1 : "+testUF(u1,op)+" s");

        UnionFindV2 u2 = new UnionFindV2(n);
        System.out.println("U2 : "+testUF(u2,op)+" s");

        UnionFindV3 u3 = new UnionFindV3(n);
        System.out.println("U3 : "+testUF(u3,op)+" s");

        UnionFindV4 u4 = new UnionFindV4(n);
        System.out.println("U4 : "+testUF(u4,op)+" s");

        UnionFindV5 u5 = new UnionFindV5(n);
        System.out.println("U5 : "+testUF(u5,op)+" s");

        UnionFindV6 u6 = new UnionFindV6(n);
        System.out.println("U6 : "+testUF(u6,op)+" s");
    }

    public final void eat(){
        // 代码
    }
}
